﻿#include "CodeCraft-2021.h"

void file_init() {
	freopen("C:/Users/谭树勇/Desktop/huawei2021/CodeCraft-2021/training-data/training-1.txt", "r", stdin);
	freopen("C:/Users/谭树勇/Desktop/huawei2021/CodeCraft-2021/training-data/solution-1.txt", "w", stdout);
	log_debug = true;
	if (fopen_s(&fp, "C:/Users/lx/source/repos/huawei2021/CodeCraft-2021/training-data/debug2.txt", "w") != 0) {
		cout << "error" << endl;
	}
	WRITE_LOG("标准输入输出重定向完毕");
	WRITE_LOG("debug开关开启");
}

void init() {
	
	vm_mp.clear();

	// 读入服务器
	cin >> host_num;
	cin.get();
	for (int i = 0; i < host_num; i++) {
		string tmp_s;
		getline(cin, tmp_s);
		vector<string> vec = split(tmp_s.substr(1, tmp_s.length() - 2), ", ");
		host[i].name = vec[0];
		host[i].core = stoi(vec[1]);
		host[i].memory = stoi(vec[2]);
		host[i].purchase_cost = stoi(vec[3]);
		host[i].eletric_cost = stoi(vec[4]);
		// host[i].print();
	}
	WRITE_LOG("读入服务器数量：" + to_string(host_num));
	
	// 读入虚拟机
	cin >> vm_num;
	cin.get();
	for (int i = 0; i < vm_num; i++) {
		string tmp_s;
		getline(cin, tmp_s);
		vector<string> vec = split(tmp_s.substr(1, tmp_s.length() - 2), ", ");
		vm[i].name = vec[0];
		vm[i].core = stoi(vec[1]);
		vm[i].memory = stoi(vec[2]);
		vm[i].is_double = stoi(vec[3]);
		// vm[i].print();
		vm_mp[vm[i].name] = i;
	}
	WRITE_LOG("读入虚拟机数量：" + to_string(vm_num));

	// 读入请求
	cin >> day_num;
	cin.get();
	for (int i = 0; i < day_num; i++) {
		cin >> day[i].num;
		cin.get();
		day[i].requests.clear();
		// day[i].print();
		for (int j = 0; j < day[i].num; j++) {
			string tmp_s;
			getline(cin, tmp_s);
			vector<string> vec = split(tmp_s.substr(1, tmp_s.length() - 2), ", ");
			Request request;
			if (vec[0] == "add") {
				request.is_add = 1;
			}
			else {
				request.is_add = 0;
			}
			if (request.is_add == 0) {
				request.request_id = stoi(vec[1]);
			}
			else {
				request.vm = vm[vm_mp[vec[1]]];
				request.request_id = stoi(vec[2]);
			}
			// request.print();
			day[i].requests.push_back(request);
			if (id_mp.count(request.request_id) == 0) {
				IDReflect reflect;
				reflect.add_day = i;
				reflect.add_idx = j;
				id_mp[request.request_id] = reflect;
			}
			else {
				id_mp[request.request_id].del_day = i;
				id_mp[request.request_id].del_idx = j;
			}
		}
	}
	WRITE_LOG("读入请求数量：" + to_string(day_num));
}

void set_host() {
	int max_memory = 0;
	int max_core = 0;
	double safe_coe = 1.2;
	int now_memory = 0;
	int now_core = 0;
	for (int i = 0; i < day_num; i++) {
		for (int j = 0; j < day[i].num; j++) {
			if (day[i].requests[j].is_add == 1) {
				now_memory += day[i].requests[j].vm.memory;
				now_core += day[i].requests[j].vm.core;
			}else{
				now_memory -= day[i].requests[j].vm.memory;
				now_core -= day[i].requests[j].vm.core;
			}
			max_memory = max(max_memory, now_memory);
			max_core = max(max_core, now_core);
		}
	}
	int max_vm_memory = 0;
	int max_vm_core = 0;
	for (int i = 0; i < vm_num; i++) {
		max_vm_memory = max(max_vm_memory, vm[i].memory);
		max_vm_core = max(max_vm_core, vm[i].core);
	}
	max_vm_memory *= 2;
	max_vm_core *= 2;
	WRITE_LOG("max_memory: " + to_string(max_memory));
	WRITE_LOG("max_core: " + to_string(max_core));
	WRITE_LOG("safe_coe: " + to_string(safe_coe));
	long long A = (int)(max_memory * safe_coe);
	long long B = (int)(max_core * safe_coe);
	WRITE_LOG("relax_memory: " + to_string(A));
	WRITE_LOG("relax_core: " + to_string(B));
	long long ans1 = LLONG_MAX, ans2 = LLONG_MAX, ans3 = LLONG_MAX;
	int pos1 = -1, pos2 = -1, pos3 = -1, pos4 = -1;
	int u1, u2, u3, u4;
	for (int i = 0; i < host_num; i++) {
		if (host[i].memory < max_vm_memory || host[i].core < max_vm_core) continue;
		long long u = A / host[i].memory + 1;
		if (u * host[i].core < B) {
			continue;
		}
		long long c = host[i].purchase_cost + host[i].eletric_cost * day_num;
		if (u * c < ans1) {
			ans1 = u * c;
			pos1 = i;
			u1 = u;
		}
	}
	for (int i = 0; i < host_num; i++) {
		if (host[i].memory < max_vm_memory || host[i].core < max_vm_core) continue;
		long long u = B / host[i].core + 1;
		if (u * host[i].memory < A) {
			continue;
		}
		long long c = host[i].purchase_cost + host[i].eletric_cost * day_num;
		if (u * c < ans2) {
			ans2 = u * c;
			pos2 = i;
			u2 = u;
		}
	}
	for (int i = 0; i < host_num - 1; i++) {
		if (host[i].memory < max_vm_memory || host[i].core < max_vm_core) continue;
		for (int j = i + 1; j < host_num; j++) {
			if (host[j].memory < max_vm_memory || host[j].core < max_vm_core) continue;
			long long ai = host[i].memory;
			long long bi = host[i].core;
			long long aj = host[j].memory;
			long long bj = host[j].core;
			if (ai * bj - bi * aj == 0) continue;
			long long ui = (A * bj - B * aj) / (ai * bj - bi * aj) + 1;
			long long uj = (A * bi - B * ai) / (aj * bi - bj * ai) + 1;
			if (ui <= 0 || uj <= 0) continue;
			long long ci = host[i].purchase_cost + host[i].eletric_cost * day_num;
			long long cj = host[j].purchase_cost + host[j].eletric_cost * day_num;
			if (ui * ci + uj * cj < ans3) {
				ans3 = ui * ci + uj * cj;
				pos3 = i;
				pos4 = j;
				u3 = ui;
				u4 = uj;
			}
		}
	}
	if (ans1 < ans2 && ans1 < ans3) {
		WRITE_LOG("选择单种服务器，采用内存对齐方式，服务器型号：");
		host[pos1].print();
		WRITE_LOG("数量为：" + to_string(u1));
		WRITE_LOG("总内存和总核心分别为：" + to_string(u1 * host[pos1].memory) + " " + to_string(u1 * host[pos1].core));
		WRITE_LOG("计算总价：" + to_string(ans1));
		WRITE_LOG("购置总价：" + to_string(u1 * host[pos1].purchase_cost));
		boughthosts.clear();
		for (int i = 0; i < u1; i++) {
			boughthosts.push_back(BoughtHost(host[pos1], i));
		}
		cout << "(purchase, 1)" << endl;
		cout << "(" << host[pos1].name << ", " << u1 << ")" << endl;
	}
	else if (ans2 < ans3 && ans2 < ans1) {
		WRITE_LOG("选择单种服务器，采用核心对齐方式，服务器型号：");
		host[pos2].print();
		WRITE_LOG("数量为：" + to_string(u2));
		WRITE_LOG("总内存和总核心分别为：" + to_string(u2 * host[pos2].memory) + " " + to_string(u2 * host[pos2].core));
		WRITE_LOG("计算总价：" + to_string(ans2));
		WRITE_LOG("购置总价：" + to_string(u2 * host[pos2].purchase_cost));
		boughthosts.clear();
		for (int i = 0; i < u2; i++) {
			boughthosts.push_back(BoughtHost(host[pos2], i));
		}
		cout << "(purchase, 1)" << endl;
		cout << "(" << host[pos2].name << ", " << u2 << ")" << endl;
	}
	else {
		WRITE_LOG("选择两种服务器，采用内存核心双对齐方式，服务器型号：");
		host[pos3].print();
		host[pos4].print();
		WRITE_LOG("数量分别为：" + to_string(u3) + " " + to_string(u4));
		WRITE_LOG("总内存和总核心分别为：" + to_string(u3 * host[pos3].memory + u4 * host[pos4].memory) + " " + 
			to_string(u3 * host[pos3].core + u4 * host[pos4].core));
		WRITE_LOG("计算总价：" + to_string(ans3));
		WRITE_LOG("购置总价：" + to_string(u3 * host[pos3].purchase_cost + u4 * host[pos4].purchase_cost));
		boughthosts.clear();
		for (int i = 0; i < u3; i++) {
			boughthosts.push_back(BoughtHost(host[pos3], i));
		}
		for (int i = 0; i < u4; i++) {
			boughthosts.push_back(BoughtHost(host[pos4], i + u3));
		}
		cout << "(purchase, 2)" << endl;
		cout << "(" << host[pos3].name << ", " << u3 << ")" << endl;
		cout << "(" << host[pos4].name << ", " << u4 << ")" << endl;
	}
}

bool is_need_move() {
	int core_use = 0, core_free = 0;
	int memory_use = 0, memory_free = 0;
	for (auto host : boughthosts) {
		if (host.used_core_A != 0 || host.used_core_B != 0 || host.used_memory_A != 0 || host.used_memory_B != 0) {
			core_use += host.used_core_A + host.used_core_B;
			core_free += host.host.core - host.used_core_A - host.used_core_B;
			memory_use += host.used_memory_A + host.used_memory_B;
			memory_free += host.host.memory - host.used_memory_A - host.used_memory_B;
		}
	}
	double core_rate = static_cast<double>(core_use) / static_cast<double>(core_use + core_free);
	double memory_rate = static_cast<double>(memory_use) / static_cast<double>(memory_use + memory_free);

	if (core_rate < VM_MOVE_RATE || memory_rate < VM_MOVE_RATE) return true;

	return false;
}

void vm_move() {
	int left = 0, right = 0;
	for (int i = boughthosts.size() - 1; i >= 0; --i) {
		if (!(boughthosts[i].used_memory_A == 0 && boughthosts[i].used_memory_B == 0 &&
			boughthosts[i].used_core_A == 0 && boughthosts[i].used_core_B == 0)) {
			right = i;
			break;
		}
	}
	int cnt = 0;
	vector<vector<string>> migrations;
	while (cnt < now_vm_cnt * 5 / 1000 && left < right) {
		for (int i = boughthosts[left].contain_vms.size() - 1; i >= 0 && cnt < now_vm_cnt * 5 / 1000; --i) {
			if (boughthosts[left].contain_vms[i].is_del) continue;
			int c = boughthosts[left].contain_vms[i].vm.core, m = boughthosts[left].contain_vms[i].vm.memory;
			int is_double = boughthosts[left].contain_vms[i].vm.is_double;
			while (left < right) {
				int free_c_A = boughthosts[right].host.core / 2 - boughthosts[right].used_core_A;
				int free_c_B = boughthosts[right].host.core / 2 - boughthosts[right].used_core_B;
				int free_m_A = boughthosts[right].host.memory / 2 - boughthosts[right].used_memory_A;
				int free_m_B = boughthosts[right].host.memory / 2 - boughthosts[right].used_memory_B;
				if (is_double) {
					if (free_c_A < c / 2 || free_c_B < c / 2 || free_m_A < m / 2 || free_m_B < m / 2) {
						right--;
						continue;
					}
					boughthosts[right].used_core_A += c / 2;
					boughthosts[right].used_core_B += c / 2;
					boughthosts[right].used_memory_A += m / 2;
					boughthosts[right].used_memory_B += m / 2;
					migrations.push_back({ to_string(boughthosts[left].contain_vms[i].vm_id), to_string(boughthosts[right].host_id) });
					break;
				}
				else {
					if ((free_c_A < c || free_m_A < m) && (free_c_B < c || free_m_B < m)) {
						right--;
						continue;
					}
					if (free_c_A >= free_c_B || free_m_A >= free_m_B) {
						if (free_c_B >= c && free_m_B >= m) {
							boughthosts[right].used_core_B += c;
							boughthosts[right].used_memory_B += m;
							migrations.push_back({ to_string(boughthosts[left].contain_vms[i].vm_id), to_string(boughthosts[right].host_id), "B" });
							break;
						}
					}
					if (free_c_A >= c && free_m_A >= m) {
						boughthosts[right].used_core_A += c;
						boughthosts[right].used_memory_A += m;
						migrations.push_back({ to_string(boughthosts[left].contain_vms[i].vm_id), to_string(boughthosts[right].host_id), "A" });
						break;
					}
					if (free_c_B >= c && free_m_B >= m) {
						boughthosts[right].used_core_B += c;
						boughthosts[right].used_memory_B += m;
						migrations.push_back({ to_string(boughthosts[left].contain_vms[i].vm_id), to_string(boughthosts[right].host_id), "B" });
						break;
					}
				}
			}
			cnt++;
		}
	}
	format_cout({"migration", to_string(cnt)});
	for (auto migration : migrations) format_cout(migration);
}

void solve(int day_index) {
	sort(boughthosts.begin(), boughthosts.end());
	if (is_need_move() && false) {
		vm_move();
		sort(boughthosts.begin(), boughthosts.end());
	}
	else format_cout({ "migration", "0" });

	vector<Request> one_day_add;
	set<int> one_day_del;
	for (auto r : day[day_index].requests) {
		if (r.is_add) one_day_add.push_back(r);
		else one_day_del.insert(r.request_id);
	}

	sort(one_day_add.begin(), one_day_add.end(), [](Request& a, Request& b) {
			return a.vm < b.vm;
		});

	map<int, int> tmp_reflect;
	for (int i = 0; i < boughthosts.size(); ++i) {
		tmp_reflect[boughthosts[i].host_id] = i;
	}


	map<int, vector<string>> vm_id_to_out;
	for (auto req : one_day_add) {
		int right = boughthosts.size();
		int left = 0;
		int c = req.vm.core, m = req.vm.memory;
		int is_double = req.vm.is_double;
		int free_c_A = boughthosts[left].host.core / 2 - boughthosts[left].used_core_A;
		int free_c_B = boughthosts[left].host.core / 2 - boughthosts[left].used_core_B;
		int free_m_A = boughthosts[left].host.memory / 2 - boughthosts[left].used_memory_A;
		int free_m_B = boughthosts[left].host.memory / 2 - boughthosts[left].used_memory_B;
		if (is_double) {
			bool tmp_flag = false;
			while (left < right && free_c_A < c / 2 || free_c_B < c / 2 || free_m_A < m / 2 || free_m_B < m / 2) {
				left++;
				free_c_A = boughthosts[left].host.core / 2 - boughthosts[left].used_core_A;
				free_c_B = boughthosts[left].host.core / 2 - boughthosts[left].used_core_B;
				free_m_A = boughthosts[left].host.memory / 2 - boughthosts[left].used_memory_A;
				free_m_B = boughthosts[left].host.memory / 2 - boughthosts[left].used_memory_B;
			}
			if (left == right) left = 0;
			while (left < right && (free_c_A < c / 2 || free_c_B < c / 2 || free_m_A < m / 2 || free_m_B < m / 2)) {
				right--;
				tmp_flag = true;
				free_c_A = boughthosts[right].host.core / 2 - boughthosts[right].used_core_A;
				free_c_B = boughthosts[right].host.core / 2 - boughthosts[right].used_core_B;
				free_m_A = boughthosts[right].host.memory / 2 - boughthosts[right].used_memory_A;
				free_m_B = boughthosts[right].host.memory / 2 - boughthosts[right].used_memory_B;
			}
			if (left == right) {
				cout << "no ans! please check the bought host! lx!" << endl;
				throw "no ans! please check the bought host! lx!";
			}
			if (tmp_flag) {
				boughthosts[right].used_core_A += c / 2;
				boughthosts[right].used_core_B += c / 2;
				boughthosts[right].used_memory_A += m / 2;
				boughthosts[right].used_memory_B += m / 2;
				DeployVM tmp_deploy_vm(req.vm, req.request_id, boughthosts[right].host_id, 2);
				deployVMs.push_back(tmp_deploy_vm);
				boughthosts[right].contain_vms.push_back(tmp_deploy_vm);
				vm_id_to_out[req.request_id] = { to_string(boughthosts[right].host_id) };
				//format_cout({ to_string(boughthosts[right].host_id) });
			}
			else {
				boughthosts[left].used_core_A += c / 2;
				boughthosts[left].used_core_B += c / 2;
				boughthosts[left].used_memory_A += m / 2;
				boughthosts[left].used_memory_B += m / 2;
				DeployVM tmp_deploy_vm(req.vm, req.request_id, boughthosts[left].host_id, 2);
				deployVMs.push_back(tmp_deploy_vm);
				boughthosts[left].contain_vms.push_back(tmp_deploy_vm);
				vm_id_to_out[req.request_id] = { to_string(boughthosts[left].host_id) };
				//format_cout({ to_string(boughthosts[left].host_id) });
			}
		}
		else {
			bool tmp_flag = false;
			while (left < right && (free_c_A < c || free_m_A < m) && (free_c_B < c || free_m_B < m)) {
				left++;
				free_c_A = boughthosts[left].host.core / 2 - boughthosts[left].used_core_A;
				free_c_B = boughthosts[left].host.core / 2 - boughthosts[left].used_core_B;
				free_m_A = boughthosts[left].host.memory / 2 - boughthosts[left].used_memory_A;
				free_m_B = boughthosts[left].host.memory / 2 - boughthosts[left].used_memory_B;
			}
			while (left < right && (free_c_A < c || free_m_A < m) && (free_c_B < c || free_m_B < m)) {
				right--;
				tmp_flag = true;
				free_c_A = boughthosts[right].host.core / 2 - boughthosts[right].used_core_A;
				free_c_B = boughthosts[right].host.core / 2 - boughthosts[right].used_core_B;
				free_m_A = boughthosts[right].host.memory / 2 - boughthosts[right].used_memory_A;
				free_m_B = boughthosts[right].host.memory / 2 - boughthosts[right].used_memory_B;
			}
			if (left == right) left = 0;
			if (left == right) {
				cout << "no ans! please check the bought host! lx!" << endl;
				throw "no ans! please check the bought host! lx!";
			}
			if (free_c_A >= free_c_B || free_m_A >= free_m_B) {
				if (free_c_B >= c && free_m_B >= m) {
					if (tmp_flag) {
						boughthosts[right].used_core_B += c;
						boughthosts[right].used_memory_B += m;
						DeployVM tmp_deploy_vm(req.vm, req.request_id, boughthosts[right].host_id, 1);
						deployVMs.push_back(tmp_deploy_vm);
						boughthosts[right].contain_vms.push_back(tmp_deploy_vm);
						vm_id_to_out[req.request_id] = { to_string(boughthosts[right].host_id), "B" };
						//format_cout({ to_string(boughthosts[right].host_id), "B" });
					}
					else {
						boughthosts[left].used_core_B += c;
						boughthosts[left].used_memory_B += m;
						DeployVM tmp_deploy_vm(req.vm, req.request_id, boughthosts[left].host_id, 1);
						deployVMs.push_back(tmp_deploy_vm);
						boughthosts[left].contain_vms.push_back(tmp_deploy_vm);
						vm_id_to_out[req.request_id] = { to_string(boughthosts[left].host_id), "B" };
						//format_cout({ to_string(boughthosts[left].host_id), "B" });
					}
					continue;
				}
			}
			if (free_c_A >= c && free_m_A >= m) {
				if (tmp_flag) {
					boughthosts[right].used_core_A += c;
					boughthosts[right].used_memory_A += m;
					DeployVM tmp_deploy_vm(req.vm, req.request_id, boughthosts[right].host_id, 0);
					deployVMs.push_back(tmp_deploy_vm);
					boughthosts[right].contain_vms.push_back(tmp_deploy_vm);
					vm_id_to_out[req.request_id] = { to_string(boughthosts[right].host_id), "A" };
					//format_cout({ to_string(boughthosts[right].host_id), "A" });
				}
				else {
					boughthosts[left].used_core_A += c;
					boughthosts[left].used_memory_A += m;
					DeployVM tmp_deploy_vm(req.vm, req.request_id, boughthosts[left].host_id, 0);
					deployVMs.push_back(tmp_deploy_vm);
					boughthosts[left].contain_vms.push_back(tmp_deploy_vm);
					vm_id_to_out[req.request_id] = { to_string(boughthosts[left].host_id), "A" };
					//format_cout({ to_string(boughthosts[left].host_id), "A" });
				}
				continue;
			}
			if (free_c_B >= c && free_m_B >= m) {
				if (tmp_flag) {
					boughthosts[right].used_core_B += c;
					boughthosts[right].used_memory_B += m;
					DeployVM tmp_deploy_vm(req.vm, req.request_id, boughthosts[right].host_id, 1);
					deployVMs.push_back(tmp_deploy_vm);
					boughthosts[right].contain_vms.push_back(tmp_deploy_vm);
					vm_id_to_out[req.request_id] = { to_string(boughthosts[right].host_id), "B" };
					//format_cout({ to_string(boughthosts[right].host_id), "B" });
				}
				else {
					boughthosts[left].used_core_B += c;
					boughthosts[left].used_memory_B += m;
					DeployVM tmp_deploy_vm(req.vm, req.request_id, boughthosts[left].host_id, 1);
					deployVMs.push_back(tmp_deploy_vm);
					boughthosts[left].contain_vms.push_back(tmp_deploy_vm);
					vm_id_to_out[req.request_id] = { to_string(boughthosts[left].host_id), "B" };
					//format_cout({ to_string(boughthosts[left].host_id), "B" });
				}
				continue;
			}
		}
		now_vm_cnt++;
	}


	for (auto r : day[day_index].requests) {
		if (r.is_add) {
			format_cout(vm_id_to_out[r.request_id]);
		}
	}

	for (auto deploy : deployVMs) {
		if (one_day_del.count(deploy.vm_id) > 0) {
			deploy.is_del = 1;
			int c = deploy.vm.core, m = deploy.vm.memory;
			if (deploy.vm.is_double) {
				boughthosts[tmp_reflect[deploy.host_id]].used_core_A -= c / 2;
				boughthosts[tmp_reflect[deploy.host_id]].used_core_B -= c / 2;
				boughthosts[tmp_reflect[deploy.host_id]].used_memory_A -= m / 2;
				boughthosts[tmp_reflect[deploy.host_id]].used_memory_B -= m / 2;
			}
			else {
				if (deploy.type == 0) {
					boughthosts[tmp_reflect[deploy.host_id]].used_core_A -= c;
					boughthosts[tmp_reflect[deploy.host_id]].used_memory_A -= m;
				}
				else if (deploy.type == 1) {
					boughthosts[tmp_reflect[deploy.host_id]].used_core_B -= c;
					boughthosts[tmp_reflect[deploy.host_id]].used_memory_B -= m;
				}
			}
		}
	}

	for (auto host : boughthosts) {
		if (host.used_core_A != 0 || host.used_core_B != 0 || host.used_memory_A != 0 || host.used_memory_B != 0) {
			power_cost += host.host.eletric_cost;
		}
	}
}

vector<int> dp_for_space(int memory, int core, vector<int>& flag, int day_idx, int is_double) {
	//cout << "dp_for_space" << endl;
	double coe = 0.95;
	vector<int> ans_vec;
	if (is_double == 0) {
		//cout << "is_double no" << endl;
		//cout << memory << " " << core << endl;
		for (int i = 0; i <= memory; i++) {
			for (int j = 0; j <= core; j++) {
				dp[i][j] = false;
				sol[i][j] = -1;
			}
		}
		//cout << memory << " " << core << endl;
		dp[0][0] = true;
		int out_flag = 0;
		int out_memory = -1;
		int out_core = -1;
		for (int i = 0; i < day[day_idx].requests.size(); i++) {
			if (out_flag == 1) break;
			if (flag[i] == 1 || day[day_idx].requests[i].is_add == 0 || day[day_idx].requests[i].vm.is_double == 1) continue;
			int x = day[day_idx].requests[i].vm.memory;
			int y = day[day_idx].requests[i].vm.core;
			for (int j = memory; j >= x; j--) {
				if (out_flag == 1) break;
				for (int k = core; k >= y; k--) {
					if (dp[j - x][k - y]) {
						dp[j][k] = true;
						sol[j][k] = i;
						if (j >= coe * memory && k >= coe * core) {
							out_flag = 1;
							out_memory = j;
							out_core = k;
							break;
						}
					}
				}
			}
		}
		//cout << "out" << endl;
		if (out_flag == 0) {
			int tmp_coe = -1;
			for (int j = memory; j >= 0; j--) {
				for (int k = core; k >= 0; k--) {
					if (dp[j][k] && j * 1.0 / memory + k * 1.0 / core > tmp_coe) {
						tmp_coe = j * 1.0 / memory + k * 1.0 / core;
						out_memory = j;
						out_core = k;
					}
				}
			}
		}
		while (out_memory > 0 && out_core > 0) {
			int pos = sol[out_memory][out_core];
			ans_vec.push_back(pos);
			out_memory -= day[day_idx].requests[pos].vm.memory;
			out_core -= day[day_idx].requests[pos].vm.core;
		}
	}
	else {
		//cout << "is_double yes" << endl;
		memory /= 2;
		core /= 2;
		//cout << memory << " " << core << endl;
		for (int i = 0; i <= memory; i++) {
			for (int j = 0; j <= core; j++) {
				dp[i][j] = false;
				sol[i][j] = -1;
			}
		}
		dp[0][0] = true;
		int out_flag = 0;
		int out_memory = -1;
		int out_core = -1;
		for (int i = 0; i < day[day_idx].requests.size(); i++) {
			if (out_flag == 1) break;
			if (flag[i] == 1 || day[day_idx].requests[i].is_add == 0 || day[day_idx].requests[i].vm.is_double == 0) continue;
			int x = day[day_idx].requests[i].vm.memory / 2;
			int y = day[day_idx].requests[i].vm.core / 2;
			for (int j = memory; j >= x; j--) {
				if (out_flag == 1) break;
				for (int k = core; k >= y; k--) {
					if (dp[j - x][k - y]) {
						dp[j][k] = true;
						sol[j][k] = i;
						if (j >= coe * memory && k >= coe * core) {
							out_flag = 1;
							out_memory = j;
							out_core = k;
							break;
						}
					}
				}
			}
		}
		if (out_flag == 0) {
			int tmp_coe = -1;
			for (int j = memory; j >= 0; j--) {
				for (int k = core; k >= 0; k--) {
					if (dp[j][k] && j * 1.0 / memory + k * 1.0 / core > tmp_coe) {
						tmp_coe = j * 1.0 / memory + k * 1.0 / core;
						out_memory = j;
						out_core = k;
					}
				}
			}
		}
		while (out_memory > 0 && out_core > 0) {
			int pos = sol[out_memory][out_core];
			ans_vec.push_back(pos);
			out_memory -= day[day_idx].requests[pos].vm.memory / 2;
			out_core -= day[day_idx].requests[pos].vm.core / 2;
		}
	}
	//cout << "quit dp_for_space" << endl;
	return ans_vec;
}

void update_information(vector<int>& vm_sol, int host_pos, int day_idx, vector<int>& flag, int type) {
	for (auto x : vm_sol) {
		flag[x] = 1;
	}
	if (type == 0) {
		boughthosts[host_pos].use_for = 0;
		for (auto x : vm_sol) {
			DeployVM deployVM(day[day_idx].requests[x].vm, day[day_idx].requests[x].request_id, host_pos, type);
			deployVMs.push_back(deployVM);
			deploy_id_to_deployVM_mp[day[day_idx].requests[x].request_id] = deployVMs.size() - 1;
			boughthosts[host_pos].used_memory_A += day[day_idx].requests[x].vm.memory;
			boughthosts[host_pos].used_core_A += day[day_idx].requests[x].vm.core;
		}
	}
	else if (type == 1) {
		boughthosts[host_pos].use_for = 0;
		for (auto x : vm_sol) {
			DeployVM deployVM(day[day_idx].requests[x].vm, day[day_idx].requests[x].request_id, host_pos, type);
			deployVMs.push_back(deployVM);
			deploy_id_to_deployVM_mp[day[day_idx].requests[x].request_id] = deployVMs.size() - 1;
			boughthosts[host_pos].used_memory_B += day[day_idx].requests[x].vm.memory;
			boughthosts[host_pos].used_core_B += day[day_idx].requests[x].vm.core;
		}
	}
	else {
		boughthosts[host_pos].use_for = 1;
		for (auto x : vm_sol) {
			DeployVM deployVM(day[day_idx].requests[x].vm, day[day_idx].requests[x].request_id, host_pos, type);
			deployVMs.push_back(deployVM);
			deploy_id_to_deployVM_mp[day[day_idx].requests[x].request_id] = deployVMs.size() - 1;
			boughthosts[host_pos].used_memory_A += day[day_idx].requests[x].vm.memory / 2;
			boughthosts[host_pos].used_core_A += day[day_idx].requests[x].vm.core / 2;
			boughthosts[host_pos].used_memory_B += day[day_idx].requests[x].vm.memory / 2;
			boughthosts[host_pos].used_core_B += day[day_idx].requests[x].vm.core / 2;
		}
	}
}

void fix_distributed_host(int day_idx, vector<int>& flag) {
	//cout << "fix_distributed_host" << endl;
	for (int i = 0; i < boughthosts.size(); i++) {
		if (boughthosts[i].use_for == -1) continue;
		if (boughthosts[i].use_for == 0) {
			vector<int> vm_sol = dp_for_space(boughthosts[i].host.memory / 2 - boughthosts[i].used_memory_A,
				boughthosts[i].host.core / 2 - boughthosts[i].used_core_A, flag, day_idx, 0);
			update_information(vm_sol, i, day_idx, flag, 0);
			vm_sol = dp_for_space(boughthosts[i].host.memory / 2 - boughthosts[i].used_memory_B,
				boughthosts[i].host.core / 2 - boughthosts[i].used_core_B, flag, day_idx, 0);
			update_information(vm_sol, i, day_idx, flag, 1);
		}
		else {
			vector<int> vm_sol = dp_for_space(boughthosts[i].host.memory - boughthosts[i].used_memory_A * 2,
				boughthosts[i].host.core - boughthosts[i].used_core_A * 2, flag, day_idx, 1);
			update_information(vm_sol, i, day_idx, flag, 2);
		}
	}
}

void distribute_by_lx(int day_idx, vector<int>& flag) {
	//cout << "distribute_by_lx" << endl;
	int host_pos = -1;
	if (day_idx % 2 == 0) {
		for (int i = 0; i < boughthosts.size(); i++) {
			if (boughthosts[i].use_for == -1) {
				host_pos = i;
				break;
			}
		}
	}
	else {
		for (int i = boughthosts.size() - 1; i >= 0; i--) {
			if (boughthosts[i].use_for == -1) {
				host_pos = i;
				break;
			}
		}
	}
	if (host_pos == -1) {
		WRITE_LOG("剩余物理机数量不足");
	}
	int vm_pos = -1;
	for (int j = 0; j < day[day_idx].requests.size(); j++) {
		if (flag[j] == 0 && day[day_idx].requests[j].is_add == 1) {
			vm_pos = j;
			break;
		}
	}
	if (vm_pos == -1) {
		WRITE_LOG("所有虚拟机均已分配");
	}
	if (day[day_idx].requests[vm_pos].vm.is_double == 1) {
		vector<int> vm_sol = dp_for_space(boughthosts[host_pos].host.memory - boughthosts[host_pos].used_memory_A * 2,
			boughthosts[host_pos].host.core - boughthosts[host_pos].used_core_A * 2, flag, day_idx, 1);
		update_information(vm_sol, host_pos, day_idx, flag, 2);
	}
	else {
		vector<int> vm_sol = dp_for_space(boughthosts[host_pos].host.memory / 2 - boughthosts[host_pos].used_memory_A,
			boughthosts[host_pos].host.core / 2 - boughthosts[host_pos].used_core_A, flag, day_idx, 0);
		update_information(vm_sol, host_pos, day_idx, flag, 0);
		vm_sol = dp_for_space(boughthosts[host_pos].host.memory / 2 - boughthosts[host_pos].used_memory_B,
			boughthosts[host_pos].host.core / 2 - boughthosts[host_pos].used_core_B, flag, day_idx, 0);
		update_information(vm_sol, host_pos, day_idx, flag, 1);
	}
}

void delete_vm_machine(int day_idx) {
	//cout << "delete_vm_machine" << endl;
	for (int i = 0; i < day[day_idx].requests.size(); i++) {
		if (day[day_idx].requests[i].is_add == 1) continue;
		DeployVM tmp_vm = deployVMs[deploy_id_to_deployVM_mp[day[day_idx].requests[i].request_id]];
		tmp_vm.is_del = 1;
		if (tmp_vm.type == 0) {
			boughthosts[tmp_vm.host_id].used_core_A -= tmp_vm.vm.core;
			boughthosts[tmp_vm.host_id].used_memory_A -= tmp_vm.vm.memory;
		}
		else if (tmp_vm.type == 1) {
			boughthosts[tmp_vm.host_id].used_core_B -= tmp_vm.vm.core;
			boughthosts[tmp_vm.host_id].used_memory_B -= tmp_vm.vm.memory;
		}
		else {
			boughthosts[tmp_vm.host_id].used_core_A -= tmp_vm.vm.core / 2;
			boughthosts[tmp_vm.host_id].used_memory_A -= tmp_vm.vm.memory / 2;
			boughthosts[tmp_vm.host_id].used_core_B -= tmp_vm.vm.core / 2;
			boughthosts[tmp_vm.host_id].used_memory_B -= tmp_vm.vm.memory / 2;
		}
	}
}

void naive_solve() {
	deploy_id_to_deployVM_mp.clear();
	deployVMs.clear();
	for (int i = 0; i < day_num; i++) {
		
		vector<int> flag;
		for (int j = 0; j < day[i].requests.size(); j++) {
			flag.push_back(0);
		}
		fix_distributed_host(i, flag);
		int while_flag = 1;
		while (while_flag == 1) {
			while_flag = 0;
			for (int j = 0; j < day[i].requests.size(); j++) {
				if (flag[j] == 0 && day[i].requests[j].is_add == 1) {
					while_flag = 1;
					break;
				}
			}
			if (while_flag == 1) {
				distribute_by_lx(i, flag);
			}
		}
		delete_vm_machine(i);
		if (i != 0) {
			cout << "(purchase, 0)" << endl;
		}
		cout << "(migration, 0)" << endl;
		for (int j = 0; j < day[i].requests.size(); j++) {
			if (day[i].requests[j].is_add == 0) continue;
			DeployVM tmp_vm = deployVMs[deploy_id_to_deployVM_mp[day[i].requests[j].request_id]];
			if (tmp_vm.type != 2) {
				if (tmp_vm.type == 0) {
					cout << "(" << tmp_vm.host_id << ", A)" << endl;
				}
				else {
					cout << "(" << tmp_vm.host_id << ", B)" << endl;
				}
			}
			else {
				cout << "(" << tmp_vm.host_id << ")" << endl;
			}
		}
		for (auto host : boughthosts) {
			if (host.used_core_A != 0 || host.used_core_B != 0 || host.used_memory_A != 0 || host.used_memory_B != 0) {
				power_cost += host.host.eletric_cost;
			}
		}
	}
	WRITE_LOG("耗电量总花费：" + to_string(power_cost));
}

int main() {
	// 输入输出重定向 debug开关
	//file_init();
	// 读入数据
	init();
	// 配置服务器数量
	set_host();
	// baseline解法
	//naive_solve();
	//boughthosts[0].host.print();
	solve(0);
	for (int i = 1; i < day_num; ++i) {
		format_cout({ "purchase", "0" });
		//cout << "nums->" << i << endl;
		solve(i);
	}
	WRITE_LOG("耗电量总花费：" + to_string(power_cost));
	return 0;
}
